package com.cheung.leetcode.stackandqueue;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.stackandqueue
 * @Author :  cheungming
 * @CreateTime : 2024-05-13 12:30:46
 * @Description : 滑动窗口
 * @Version : 1.0
 */
public class Code239Test {

    public int[] maxSlidingWindow(int[] nums, int k) {

        Deque<Integer> deque = new LinkedList<>();
        // 先处理前k个元素
        for (int i = 0; i < k; i++) {
            // 如果队列不为空，并且当前元素大于队列的最后一个元素，就删除最后一个元素
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            // 将当前元素加入
            deque.offerLast(i);
        }


        int n = nums.length;
        int[] result = new int[n - k + 1];
        result[0] = nums[deque.peekFirst()];
        // 从第k+1个元素开始
        for (int i = k; i < n; i++) {
            // 如果队列不为空，并且当前元素大于队列的最后一个元素，就删除最后一个元素
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);

            // 如果
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            result[i - k + 1] = nums[deque.peekFirst()];

        }

        return result;

    }

    @Test
    public void test1() {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] result = {3, 3, 5, 5, 6, 7};

        assert Arrays.equals(result, maxSlidingWindow(nums, k));
    }


    @Test
    public void test2() {
        int[] nums = {1};
        int k = 1;

        int[] result = {1};

        assert Arrays.equals(result, maxSlidingWindow(nums, k));
    }
}
